HedgeDoc - Collaborative markdown notes

Claim

CUE’s merge operation is a commutative partial monoid.

Proof

We will show that merge operation is associative, has an identity element, and is commutative.

Let each JSON object be a set of key-value pairs $k_i : v_i$ where $k_i$ represents keys and $v_i$ values.

Note that CUE’s merge operation can fail under certain conditions, e.g. duplicate keys or unsatisfied constraints. Hence we call the merge operation partial. For the rest of the proof, assume our JSON objects have no duplicate keys nor unsatisfiable constraints.

Let’s demonstrate associativity. Consider three arbitrary JSON objects.

A = {k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots} B = {k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots} C = {k_{c 1} : v_{c 1}, k_{c 2} : v_{c 2}, \dots}

$A = \{k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots\} \\ B = \{k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots\} \\ C = \{k_{c1}: v_{c1}, k_{c2}: v_{c2}, \ldots\}$

Associativity

Then to prove associativity, we will show the following.

merge (A, merge (B, C)) = merge (merge (A, B), C)

$\text{merge}(A, \text{merge}(B,C)) = \text{merge}(\text{merge}(A,B),C)$

For every merge operation, we simply reduce to the union of all key-value pairs in the merge. We’ll compute the left of the above equation by first reducing $\text{merge}(B,C)$ .

D = merge (B, C) = {k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots, k_{c 1} : v_{c 1}, k_{c 2} : v_{c 2}, \dots} merge (A, D) = {k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots, k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots, k_{c 1} : v_{c 1}, k_{c 2} : v_{c 2}, \dots}

$D = \text{merge}(B,C) = \{k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots, k_{c1}: v_{c1}, k_{c2}: v_{c2}, \ldots\} \\ \text{merge}(A,D) = \{k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots, k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots, k_{c1}: v_{c1}, k_{c2}: v_{c2}, \ldots \}$

We then perform a similar reduction for the right side.

E = merge (A, B) = {k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots, k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots} merge (E, C) = {k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots, k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots, k_{c 1} : v_{c 1}, k_{c 2} : v_{c 2}, \dots}

$E = \text{merge}(A,B) = \{k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots,k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots\} \\ \text{merge}(E,C) = \{k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots,k_{b1}: v_{b1}, k_{b2}: v_{b2},\ldots,k_{c1}: v_{c1}, k_{c2}: v_{c2}, \ldots\}$

Thus merge is associative.

Identity

Our identity element is the empty JSON object $\{\}$ . Note the following for any JSON object $A$ .

merge (A, {}) = A

$\text{merge}(A,\{\}) = A$

Commutativity

Like our associativity demonstration, this follows from simple reduction.

Given arbitrary JSON objects $A,B$ , we will show that $\text{merge}(A,B) = \text{merge}(B,A)$ .

A = {k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots} B = {k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots} \begin{aligned} merge (A, B) & = {k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots, k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots} \\ = {k_{b 1} : v_{b 1}, k_{b 2} : v_{b 2}, \dots, k_{a 1} : v_{a 1}, k_{a 2} : v_{a 2}, \dots} \\ = merge (B, A) \end{aligned}

$A = \{k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots\} \\ B = \{k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots\} \\ \begin{aligned} \text{merge}(A,B) &= \{k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots,k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots\} \\ &= \{k_{b1}: v_{b1}, k_{b2}: v_{b2}, \ldots,k_{a1}: v_{a1}, k_{a2}: v_{a2}, \ldots\} \\ &= \text{merge}(B,A) \end{aligned}$

Thus merge is commutative.

Conclusion

Since our partial operation merge is commutative, associative, and has an identity element, then it is a commutative partial monoid.

\begin{matrix} ◼ \end{matrix}

$\tag*{$\blacksquare$}$